﻿#include <conio.h>
#include <stdio.h>

#define Maxn 20

/*!
	\brief Hàm in cấu hình của 1 hoán vị
	\param	n	Số lượng phần tử
	\param 	a	Mảng lưu cấu hình hoán vị
*/

int Ghi(int n,int *a)
{
	for (int i=1; i<=n; i++)
		printf("%d ",a[i]);
	printf("\n");
	return 0;
}

/*!
*	\brief Hàm sinh tất cả các hoán vị bằng đệ quy
*	\param	n	Số lượng phần tử
*	\param 	i	Vị trí phần tử thứ i đang đc xét (1<=i<=n)
*	\param 	a	Mảng lưu cấu hình hoán vị
*	\param 	dd	Mảng đánh dấu 
*/

int Sinh_HV(int n,int i,int *a,int *dd)
{
	if (i>n) {
		Ghi(n,a);
		return 0;
	}
	for (int j=1; j<=n; j++)
		if (dd[j] == 0) {
			a[i] = j; 
			dd[j] = 1; 
			Sinh_HV(n,i+1,a,dd); 
			a[i] = 0; 
			dd[j] = 0;
		}
	return 0;
}

int main()
{
	int n; 
	int a[Maxn],dd[Maxn];
	printf("\nNhap n = ");
	scanf("%d", &n);
	for (int i=1; i<=n; i++) dd[i] = 0;
	Sinh_HV(n,1,a,dd);	
	return 0;
}